P2542 [AHOI2005] 航线规划

删除边不好做，考虑将操作离线倒着加边。

考虑连边时维护割边。

• $u,v$ 不联通，直接连上即可，可以看出，这条边是割边。

• $u,v$ 已经联通，说明构成一个环，原来在 $u \to v$ 路径上的边都不再是割边。

如果把割边的值设为 $1$ ，非割边的值设为 $0$ ，那么只需要修改和维护链的和即可。

因为根会变，所以边的信息需要新建点来存储。

#include <map>
#include <cstdio>
#include <iostream>
using namespace std;

const int MAXN = 2e5;
struct node {
    int ch[ 2 ] , fa;
    int val , Sum;
    bool rev , cov;
};
struct LinkCutTree {
    node Tree[ MAXN + 5 ];
    #define ls( x ) Tree[ x ].ch[ 0 ]
    #define rs( x ) Tree[ x ].ch[ 1 ]

    void Pushup( int x ) {
        Tree[ x ].Sum = Tree[ ls( x ) ].Sum + Tree[ x ].val + Tree[ rs( x ) ].Sum;
    }
    void Reverse( int x ) { swap( ls( x ) , rs( x ) ); Tree[ x ].rev ^= 1; }
    void Cov( int x ) { Tree[ x ].Sum = Tree[ x ].val = 0; Tree[ x ].cov = 1; }
    void Pushdown( int x ) {
        if( Tree[ x ].rev ) {
            if( ls( x ) ) Reverse( ls( x ) );
            if( rs( x ) ) Reverse( rs( x ) );
            Tree[ x ].rev = 0;
        }
        if( Tree[ x ].cov ) {
            if( ls( x ) ) Cov( ls( x ) );
            if( rs( x ) ) Cov( rs( x ) );
            Tree[ x ].cov = 0;
        }
    }
    
    bool isrt( int x ) { //是否为 splay 的 rt
        return ls( Tree[ x ].fa ) != x && rs( Tree[ x ].fa ) != x;
    }
    bool chk( int x ) { return rs( Tree[ x ].fa ) == x; }
    void Rotate( int x ) {
        int y = Tree[ x ].fa , z = Tree[ y ].fa , p = chk( x ) , a = Tree[ x ].ch[ !p ];
        if( !isrt( y ) ) Tree[ z ].ch[ chk( y ) ] = x; Tree[ x ].fa = z;
        Tree[ x ].ch[ !p ] = y; Tree[ y ].fa = x;
        Tree[ y ].ch[ p ] = a; if( a ) Tree[ a ].fa = y;
        Pushup( y ); 
    }
    void Pushcn( int x ) { //pushdown 根到x
        if( !isrt( x ) ) Pushcn( Tree[ x ].fa );
        Pushdown( x );
    }
    void Splay( int x ) {
        Pushcn( x );
        while( !isrt( x ) ) {
            int y = Tree[ x ].fa , z = Tree[ y ].fa;
            if( !isrt( y ) ) Rotate( chk( x ) == chk( y ) ? y : x );
            Rotate( x );
        }
        Pushup( x );
    }

    void Access( int x ) {
        for( int y = 0 ; x ; y = x , x = Tree[ x ].fa )
            Splay( x ) , rs( x ) = y , Pushup( x );
    }
    void Makeroot( int x ) {
        Access( x ); Splay( x );
        Reverse( x );
    }
    int Findroot( int x ) {
        Access( x ); Splay( x );
        for( ; ls( x ) ; x = ls( x ) ) Pushdown( x );
        Splay( x ); return x;
    }
    bool Connected( int u , int v ) {
        Makeroot( u ); return Findroot( v ) == u;
    }
    bool Link( int u , int v ) {
        if( Connected( u , v ) ) {
            Split( u , v ); Cov( v );
            return 0;
        }
        Tree[ u ].fa = v; return 1;
    }
    bool Cut( int u , int v ) {
        if( !Connected( u , v ) ) return 0;
        if( ls( v ) || Tree[ v ].fa != u ) return 0;
        Tree[ v ].fa = 0; rs( u ) = 0;
        return 1;
    }
    void Split( int u , int v ) {
        Makeroot( u ); Access( v ); Splay( v );
    }
}LCT;

struct Query {
    int op , u , v , Ans;
}Qry[ MAXN + 5 ];
map< int , bool > Graph[ MAXN + 5 ];
int n , m , q , cnt;
int main( ) {
    scanf("%d %d",&n,&m);
    for( int i = 1 , u , v ; i <= m ; i ++ ) {
        scanf("%d %d",&u,&v);
        Graph[ u ][ v ] = Graph[ v ][ u ] = 1;
        LCT.Tree[ n + i ].val = 1;
    }
    for( ; scanf("%d",&Qry[ ++ q ].op) && Qry[ q ].op != -1 ; ) {
        scanf("%d %d",&Qry[ q ].u,&Qry[ q ].v);
        if( Qry[ q ].op == 0 ) Graph[ Qry[ q ].u ][ Qry[ q ].v ] = Graph[ Qry[ q ].v ][ Qry[ q ].u ] = 0;
    } q --;
    for( int i = 1 ; i <= n ; i ++ )
        for( auto v : Graph[ i ] )
            if( v.second != 0 && v.first > i ) {
                cnt ++;
                LCT.Link( i , n + cnt ); 
                LCT.Link( n + cnt , v.first );
                //printf("%d %d\n", i , v.first );
            }
    for( int i = q ; i >= 1 ; i -- ) {
        if( Qry[ i ].op == 0 ) {
            cnt ++;
            LCT.Link( Qry[ i ].u , n + cnt );
            LCT.Link( n + cnt , Qry[ i ].v );
        }
        if( Qry[ i ].op == 1 ) {
            LCT.Split( Qry[ i ].u , Qry[ i ].v );
            Qry[ i ].Ans = LCT.Tree[ Qry[ i ].v ].Sum;
        }
    }
    for( int i = 1 ; i <= q ; i ++ )
        if( Qry[ i ].op == 1 ) printf("%d\n", Qry[ i ].Ans );
    return 0;
}